package offerv1;

import leetcodev1.链表.Solution;

public class Offer12 {

    public static void main(String[] args) {
        Offer12 offer12 = new Offer12();
        System.out.println(offer12.exist(new char[][]{{'a', 'b'}}, "ba"));
    }

    public boolean exist(char[][] board, String word) {
        if (board == null || board[0] == null || word == null) {
            return false;
        }
        int rows = board.length, columns = board[0].length, n = word.length();
        boolean[][] visited = new boolean[rows][columns];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (helper(board, word, 0, j, i, rows, columns, n, visited)) {
                    return true;
                }
            }
        }

        return false;
    }

    private boolean helper(char[][] board, String word, int index, int x, int y, int rows, int columns, int n, boolean[][] visited) {
        if (index == n) {
            return true;
        }

        if (x < 0 || x >= columns || y < 0 || y >= rows) {
            return false;
        }

        if (visited[y][x]) {
            return false;
        }

        if (board[y][x] != word.charAt(index)) {
            return false;
        }

        visited[y][x] = true;
        boolean ret = helper(board, word, index + 1, x + 1, y, rows, columns, n, visited) ||
                helper(board, word, index + 1, x - 1, y, rows, columns, n, visited) ||
                helper(board, word, index + 1, x, y + 1, rows, columns, n, visited) ||
                helper(board, word, index + 1, x, y - 1, rows, columns, n, visited);
        visited[y][x] = false;
        return ret;
    }
}

class Answer12 {
    public boolean exist(char[][] board, String word) {
        int h = board.length, w = board[0].length;
        boolean[][] visited = new boolean[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                boolean flag = check(board, visited, i, j, word, 0);
                if (flag) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
        if (board[i][j] != s.charAt(k)) {
            return false;
        } else if (k == s.length() - 1) {
            return true;
        }
        visited[i][j] = true;
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        boolean result = false;
        for (int[] dir : directions) {
            int newi = i + dir[0], newj = j + dir[1];
            if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {
                if (!visited[newi][newj]) {
                    boolean flag = check(board, visited, newi, newj, s, k + 1);
                    if (flag) {
                        result = true;
                        break;
                    }
                }
            }
        }
        visited[i][j] = false;
        return result;
    }
}
